/**
 * @file     firstBadVersion.ts
 * @brief    [278. 第一个错误的版本](https://leetcode.cn/problems/first-bad-version/description/)
 * @author   Zhu
 * @date     2022-11-05 21:17
 */

/**
 * The knows API is defined in the parent class Relation.
 * isBadVersion(version: number): boolean {
 *     ...
 * };
 */

// 递归二分
var solution = function (isBadVersion: any) {
    function seek(left: number, right: number): number {
        if (left >= right) return right;
        let mid = Math.floor((right - left) / 2) + left;
        return isBadVersion(mid) ? seek(left, mid) : seek(mid + 1, right);
    }

    return function (n: number): number {
        return seek(1, n);
    };
};

// 迭代二分
var solution = function (isBadVersion: any) {
    return function (n: number): number {
        let left = 1;
        let right = n;
        while (left < right) {
            let mid = Math.floor((right - left) / 2) + left;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    };
};
